/*
 * @lc app=leetcode.cn id=127 lang=javascript
 *
 * [127] 单词接龙
 */

// @lc code=start
/**
 * @param {string} beginWord
 * @param {string} endWord
 * @param {string[]} wordList
 * @return {number}
 */
var ladderLength = function (beginWord, endWord, wordList) {
  const wordSet = new Set([...wordList]);

  if (wordSet.size === 0 || !wordSet.has(endWord)) {
    return 0;
  }

  /**
   * @type {Set<string>}
   */
  const visited = new Set();
  /**
   * @type {Set<string>}
   */
  let beginVisited = new Set();
  beginVisited.add(beginWord);
  /**
   * @type {Set<string>}
   */
  let endVisited = new Set();
  endVisited.add(endWord);

  let step = 1;

  while (beginVisited.size && endVisited.size) {
    // 优先从最小的hash开始扩散
    if (beginVisited.size > endVisited.size) {
      [beginVisited, endVisited] = [endVisited, beginVisited];
    }
    /**
     * @type {Set<string>}
     */
    // 下一级的hash
    const nextVisited = new Set();
    for (let word of beginVisited) {
      const chars = word.split('');
      for (let i = 0; i < chars.length; i++) {
        const originChar = chars[i];
        for (let j = 0; j < 26; j++) {
          const char = String.fromCharCode(j + 97);
          if (originChar === char) {
            continue;
          }
          chars[i] = char;
          const nextWord = chars.join('');
          if (wordSet.has(nextWord)) {
            if (endVisited.has(nextWord)) {
              return step + 1;
            }
            if (!visited.has(nextWord)) {
              visited.add(nextWord);
              nextVisited.add(nextWord);
            }
          }
          chars[i] = originChar;
        }
      }
    }
    beginVisited = nextVisited;
    step++;
  }

  return 0;
};
// @lc code=end
